#include <cstdlib>
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#define random(l, r) (rand() % (r - l + 1) + l)
bool ___ = (srand(int(new char)), 0);
class Graph {
	public:
		struct Edge {
			int u, v, w;
		};
	protected:
		bool isw;
		int n, m, wl, wr;
		std::vector<Edge> data;
		std::map<std::pair<int, int>, bool> vis;
		void generate() {
			for (int i = 2; i <= n; i++) {
				int u = random(1, i - 1), v = i;
				if (rand() % 2) std::swap(u, v);
				vis[std::make_pair(u, v)] = vis[std::make_pair(v, u)] = 1;
				data.push_back((Edge) { u, v, random(wl, wr) });
			}
			for (int i = 1, u, v; i <= m - n + 1; i++) {
				do u = random(1, n), v = random(1, n); while(u == v || vis[std::make_pair(u, v)]);
				vis[std::make_pair(u, v)] = vis[std::make_pair(v, u)] = 1;
				data.push_back((Edge) { u, v, random(wl, wr) });
			}
			std::random_shuffle(data.begin(), data.end());
		}
	public:
		std::vector<Edge> edges() {
			return data;
		}
		void print(bool nm = true) {
			if (nm) {
				printf("%d %d\n", n, m);
			}
			for (int i = 0; i < (int)data.size(); i++) {
				if (isw) printf("%d %d %d\n", data[i].u, data[i].v, data[i].w);
				else printf("%d %d\n", data[i].u, data[i].v);
			}
		}
		Graph (int _n, int _m) {
			n = _n;
			m = _m;
			isw = false;
			generate();
		}
		Graph (int _n, int _m, int _r) {
			n = _n;
			m = _m;
			isw = true;
			wl = 1;
			wr = _r;
			generate();
		}
		Graph (int _n, int _m, int _l, int _r) {
			n = _n;
			m = _m;
			isw = true;
			wl = _l;
			wr = _r;
			generate();
		}
};
class Tree: public Graph {
	public:
		Tree(int n) : Graph(n, n - 1) {}
		Tree(int n, int r) : Graph(n, n - 1, r) {}
		Tree(int n, int l, int r) : Graph(n, n - 1, l, r) {}
};
